﻿#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

// 旋转
void rotateBoxes(vector<vector<double>>& boxes, const double rot) {
    for (auto& box : boxes) {
        double x_left = box[0], y_down = box[1], x_right = box[2], y_up = box[3];
        double center_x = (x_left + x_right) / 2, center_y = (y_down + y_up) / 2;

        // 旋转后的坐标
        double new_x_left = center_x + (x_left - center_x) * cos(rot) - (y_down - center_y) * sin(rot);
        double new_y_down = center_y + (x_left - center_x) * sin(rot) + (y_down - center_y) * cos(rot);
        double new_x_right = center_x + (x_right - center_x) * cos(rot) - (y_up - center_y) * sin(rot);
        double new_y_up = center_y + (x_right - center_x) * sin(rot) + (y_up - center_y) * cos(rot);

        box[0] = new_x_left;
        box[1] = new_y_down;
        box[2] = new_x_right;
        box[3] = new_y_up;
    }
}


// 计算其中心点坐标 center_x 和 center_y
// 然后x' = x⋅sin(rot) - y⋅sin(rot) + center_x
// y' = x⋅sin(rot) + y⋅cos(rot) + center_y
// 更新方框的四个顶点坐标



// 判断完美线段
vector<vector<double>> findPerfectSegments(vector<vector<double>>& boxes, vector<vector<vector<double>>>& lines, int w, int h) {
    vector<vector<double>> result;
    for (const auto& line : lines) {
        bool isPerfect = true;
        double x1 = line[0][0], y1 = line[0][1], x2 = line[1][0], y2 = line[1][1];

        // 检查线段上的每个点是否都在方框内
        for (double t = 0; t <= 1; t += 0.001) {
            double x = x1 + (x2 - x1) * t;
            double y = y1 + (y2 - y1) * t;
            bool inBox = false;
            for (const auto& box : boxes) {
                double x_left = box[0], y_down = box[1], x_right = box[2], y_up = box[3];
                if (x >= x_left && x <= x_right && y >= y_down && y <= y_up) {
                    inBox = true;
                    break;
                }
            }
            if (!inBox) {
                isPerfect = false;
                break;
            }
        }

        if (isPerfect && ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) > 30 * 30)) {
            result.push_back({ x1, y1, x2, y2 });
        }
    }
    return result;
}

// 对于每条线段，使用参数化方程表示线段上的点，并检查这些点是否都在某个方框内。
// 如果线段上的点都在方框内，并且线段的长度大于30个像素(30*30)，则认为这是一条完美线段。
// 将完美线段的端点坐标添加到结果列表中

// 计算线段与方框的交点
vector<vector<double>> findIntersections(const vector<double>& box, const vector<double>& line) {
    vector<vector<double>> intersections;
    double x_left = box[0], y_down = box[1], x_right = box[2], y_up = box[3];
    double x1 = line[0], y1 = line[1], x2 = line[2], y2 = line[3];

    // 分别计算线段与方框的四条边的交点
    vector<double> a1 = { x_left, y_down, x_left, y_up };
    vector<double> a2 = { x_left, y_up, x_right, y_up };
    vector<double> a3 = { x_right, y_up, x_right, y_down };
    vector<double> a4 = { x_right, y_down, x_left, y_down };
    vector<vector<double>> a;
    a.push_back(a1);
    a.push_back(a2);
    a.push_back(a3);
    a.push_back(a4);

    for (int i = 0; i < a.size(); ++i)
    {
        double denom = (x1 - x2) * (a[i][1] - a[i][3]) + (y1 - y2) * (a[i][2] - a[i][0]);
        if (denom == 0) intersections.push_back({ 0, 0 });

        double t = ((x1 - a[i][0]) * (a[i][1] - a[i][3]) + (y1 - a[i][1]) * (a[i][2] - a[i][0])) / denom;
        double u = -((x1 - a[i][2]) * (y1 - a[i][1]) + (y1 - a[i][3]) * (x1 - a[i][0])) / denom;

        if (t > 0 && t < 1 && u > 0 && u < 1) {
            double intersection_x = x1 + t * (x2 - x1);
            double intersection_y = y1 + t * (y2 - y1);
            intersections.push_back({ intersection_x, intersection_y });
        }
    }


    return intersections;
}

// 对于每条边，使用直线方程表示边和线段，然后计算它们的交点
// denom=(x1−x2)(y3−y4) + (y1−y2)(x4−x3)
// t= ((x1−x3)(y3−y4) + (y1−y3)(x4−x3))  /  denom
// u= −((x1−x4)(y1−y3) + (y1−y4)(x1−x3))  /  denom
//  (x1, y1) 和 (x2, y2) 是线段的端点，(x3, y3) 和 (x4, y4) 是方框边的端点
//  如果 t 和 u 都在0到1之间，说明交点在线段和方框边上，将交点坐标添加到结果列表

int main() {
    // 示例输入
    vector<vector<double>> boxes = {
        {1, 1, 2, 2, 0}, // x_left, y_down, x_right, y_up, angle
        {3, 3, 4, 4, 0}
    };
    vector<vector<vector<double>>> lines = {
        {{{1, 1}, {4, 4}}},
        {{{5, 5}, {8, 8}}}
    };
    int w = 10, h = 10;
    rotateBoxes(boxes, 90); // 旋转角度为90

    vector<vector<double>> perfectSegments = findPerfectSegments(boxes, lines, w, h);

    for (const auto& segment : perfectSegments) {
        cout << "(" << segment[0] << ", " << segment[1] << ") -> (" << segment[2] << ", " << segment[3] << ")" << endl;
    }
    for (const auto& segment : perfectSegments) {
        vector<vector<double>> intersections = findIntersections(boxes[0], segment);
        for (const auto& intersection : intersections) {
            cout << "Intersection: (" << intersection[0] << ", " << intersection[1] << ")" << endl;
        }
    }

    return 0;
}